Consider the table in http://www.survivorgrid.com/ which can be seen as a $32\times17$ matrix $A$ where entry $A_{ij}$ contains the point spread of team $i \in \{1, \dotsc 32\}$ in week $j \in \{1, \dotsc 17\}$. From $A$, we would like to obtain a subset of the teams $S \subset \{1, \dotsc 32\}, |S|=17$ and bijective function $\sigma : \{1, \dotsc, 17\} \to S$ such that the total point spread across 17 weeks $\sum_{i=1}^{17} A_{\sigma{(i)}i}$ is maximized.
We use dynamic programming to solve this problem. Consider $OPT[S, j]$, the maximal total point spread for a set of teams $S$ up to and including week $j$. Then, we have $OPT[S, 0] = 0$ and that
$OPT[S, j] = \max{\{OPT[S\setminus{\{i\}}, j-1] + A_{ij} : i \in S\}}$.
We compute $OPT[S, j]$ for $S$ with increasing cardinality and increasing values of $j$ until we obtain the final value $OPT[\{1, \dotsc 32\}, 17]$. We obtain the bijective function $\sigma$ by making the observation that $\sigma$ is only optimal if and only if
$OPT[\{\sigma{(1)}, \dotsc, \sigma{(k)}\}, k] = OPT[\{\sigma{(1)}, \dotsc, \sigma{(k-1)}\}, k-1] + A_{\sigma{(k)}k}$ for $k \in \{2, \dotsc, 17\}$
We implement this algorithm in the following section. First lets obtain $A$.
In [53]:
import requests
from bs4 import BeautifulSoup
import pandas as pd
import numpy as np
from IPython.display import HTML
In [4]:
r = requests.get('http://www.survivorgrid.com/')
In [25]:
soup = BeautifulSoup(r.text)
table = soup.find_all({'table': {'class': 'datatable tablesorter tablesorter-default'}})[5]
In [26]:
HTML(table.prettify())
Out[26]:
EV
W%
P%
Team
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Future Value
1.14
75.4%
3.2%
DEN
IND
-7.5
KC
-7.5
@SEA
+4
BYE
ARI
-8
@NYJ
-6.5
SF
-3
SD
-6.5
@NE
+1.5
@OAK
-10.5
@STL
-4
MIA
-11
@KC
-2.5
BUF
-12.5
@SD
-1.5
@CIN
-2.5
OAK
-15.5
1.08
70.5%
1.7%
SEA
GB
-6
@SD
-3
DEN
-4
BYE
@WAS
-7.5
DAL
-12.5
@STL
-5.5
@CAR
-5
OAK
-17
NYG
-11
@KC
-4
ARI
-10
@SF
+0.5
@PHI
-2
SF
-4.5
@ARI
-5
STL
-10.5
1.05
69.1%
2.8%
DET
NYG
-5.5
@CAR
+3.5
GB
+3
@NYJ
+0.5
BUF
-6
@MIN
-1
NO
+3
@ATL
+3.5
BYE
MIA
-5
@ARI
+3
@NE
+7.5
CHI
-0.5
TB
-3.5
MIN
-6
@CHI
+5
@GB
+8
1.05
72.3%
9.6%
PIT
CLE
-6.5
@BAL
+3
@CAR
+1.5
TB
-5.5
@JAX
-5.5
@CLE
-3
HOU
-7
IND
-3
BAL
-2
@NYJ
-2.5
@TEN
-2
BYE
NO
+0.5
@CIN
+2.5
@ATL
+1.5
KC
-3.5
CIN
-2.5
1.04
69.9%
4.9%
NYJ
OAK
-5.5
@GB
+10.5
CHI
+1.5
DET
-0.5
@SD
+7.5
DEN
+6.5
@NE
+10
BUF
-4
@KC
+6.5
PIT
+2.5
BYE
@BUF
+1
MIA
-2
@MIN
+1.5
@TEN
+2
NE
+5
@MIA
+3.5
1.02
81.3%
42.5%
PHI
JAX
-10
@IND
-0.5
WAS
-8.5
@SF
+5.5
STL
-6.5
NYG
-6.5
BYE
@ARI
-0.5
@HOU
-3
CAR
-6
@GB
+5.5
TEN
-9
@DAL
-3
SEA
+2
DAL
-8
@WAS
-3.5
@NYG
-1.5
1.01
66.3%
1.7%
SF
@DAL
-4.5
CHI
-7
@ARI
-3
PHI
-5.5
KC
-7.5
@STL
-4
@DEN
+3
BYE
STL
-9
@NO
+1.5
@NYG
-4.5
WAS
-11
SEA
-0.5
@OAK
-11
@SEA
+4.5
SD
-6.5
ARI
-8
1.01
66.9%
3.1%
NE
@MIA
-5
@MIN
-6.5
OAK
-15
@KC
-1.5
CIN
-6
@BUF
-6
NYJ
-10
CHI
-6
DEN
-1.5
BYE
@IND
-2
DET
-7.5
@GB
+3
@SD
-0.5
MIA
-10.5
@NYJ
-5
BUF
-11
1.00
72.6%
18.7%
CHI
BUF
-6.5
@SF
+7
@NYJ
-1.5
GB
+1.5
@CAR
+1.5
@ATL
+1.5
MIA
-7
@NE
+6
BYE
@GB
+6.5
MIN
-7.5
TB
-5
@DET
+0.5
DAL
-6.5
NO
+1.5
DET
-5
@MIN
-2.5
0.99
64.3%
0.6%
STL
MIN
-4
@TB
+2.5
DAL
-5
BYE
@PHI
+6.5
SF
+4
SEA
+5.5
@KC
+4.5
@SF
+9
@ARI
+4
DEN
+4
@SD
+5.5
OAK
-10
@WAS
PK
ARI
-1.5
NYG
-3.5
@SEA
+10.5
0.96
64.5%
5.2%
KC
TEN
-3.5
@DEN
+7.5
@MIA
-1.5
NE
+1.5
@SF
+7.5
BYE
@SD
+4
STL
-4.5
NYJ
-6.5
@BUF
-3
SEA
+4
@OAK
-6.5
DEN
+2.5
@ARI
+2
OAK
-11.5
@PIT
+3.5
SD
-1.5
0.92
60.0%
0.4%
ARI
SD
-3.5
@NYG
+1
SF
+3
BYE
@DEN
+8
WAS
-6
@OAK
-6
PHI
+0.5
@DAL
-1
STL
-4
DET
-3
@SEA
+10
@ATL
+3
KC
-2
@STL
+1.5
SEA
+5
@SF
+8
0.90
58.6%
0.7%
NO
@ATL
-3
@CLE
-6
MIN
-11.5
@DAL
-5
TB
-8
BYE
@DET
-3
GB
-2
@CAR
-2
SF
-1.5
CIN
-6
BAL
-5.5
@PIT
-0.5
CAR
-7
@CHI
-1.5
ATL
-7
@TB
-3
0.89
57.6%
0.4%
HOU
WAS
-2.5
@OAK
-3
@NYG
+3.5
BUF
-4.5
@DAL
+2
IND
+1
@PIT
+7
@TEN
+2
PHI
+3
BYE
@CLE
+1
CIN
+1.5
TEN
-3.5
@JAX
-2
@IND
+6
BAL
+2
JAX
-7
0.85
55.0%
0.3%
TB
CAR
-2.5
STL
-2.5
@ATL
+4
@PIT
+5.5
@NO
+8
BAL
+0.5
BYE
MIN
-5.5
@CLE
-1
ATL
-1.5
@WAS
+0.5
@CHI
+5
CIN
PK
@DET
+3.5
@CAR
+4
GB
+4
NO
+3
0.83
54.2%
0.4%
BAL
CIN
-1.5
PIT
-3
@CLE
-3.5
CAR
-4
@IND
+2
@TB
-0.5
ATL
-4
@CIN
+2.5
@PIT
+2
TEN
-7
BYE
@NO
+5.5
SD
-2.5
@MIA
-2
JAX
-10.5
@HOU
-2
CLE
-8.5
0.71
45.8%
0.1%
CIN
@BAL
+1.5
ATL
-3.5
TEN
-7
BYE
@NE
+6
CAR
-3.5
@IND
+2.5
BAL
-2.5
JAX
-10
CLE
-8
@NO
+6
@HOU
-1.5
@TB
PK
PIT
-2.5
@CLE
-3
DEN
+2.5
@PIT
+2.5
0.69
45.0%
0.6%
CAR
@TB
+2.5
DET
-3.5
PIT
-1.5
@BAL
+4
CHI
-1.5
@CIN
+3.5
@GB
+7.5
SEA
+5
NO
+2
@PHI
+6
ATL
-2.5
BYE
@MIN
-2
@NO
+7
TB
-4
CLE
-7
@ATL
+2.5
0.65
42.4%
0.4%
WAS
@HOU
+2.5
JAX
-6
@PHI
+8.5
NYG
-0.5
SEA
+7.5
@ARI
+6
TEN
-3.5
@DAL
+3
@MIN
+1
BYE
TB
-0.5
@SF
+11
@IND
+6
STL
PK
@NYG
+4.5
PHI
+3.5
DAL
-2.5
0.64
41.4%
0.1%
ATL
NO
+3
@CIN
+3.5
TB
-4
@MIN
-1.5
@NYG
+1
CHI
-1.5
@BAL
+4
DET
-3.5
BYE
@TB
+1.5
@CAR
+2.5
CLE
-7
ARI
-3
@GB
+7.5
PIT
-1.5
@NO
+7
CAR
-2.5
0.62
40.0%
0.2%
SD
@ARI
+3.5
SEA
+3
@BUF
-3.5
JAX
-11
NYJ
-7.5
@OAK
-7.5
KC
-4
@DEN
+6.5
@MIA
-2.5
BYE
OAK
-12.5
STL
-5.5
@BAL
+2.5
NE
+0.5
DEN
+1.5
@SF
+6.5
@KC
+1.5
0.58
35.5%
0.1%
TEN
@KC
+3.5
DAL
-2
@CIN
+7
@IND
+7
CLE
-3
JAX
-6
@WAS
+3.5
HOU
-2
BYE
@BAL
+7
PIT
+2
@PHI
+9
@HOU
+3.5
NYG
-0.5
NYJ
-2
@JAX
-1
IND
+2
0.55
35.7%
1.0%
MIN
@STL
+4
NE
+6.5
@NO
+11.5
ATL
+1.5
@GB
+12
DET
+1
@BUF
+3
@TB
+5.5
WAS
-1
BYE
@CHI
+7.5
GB
+7
CAR
+2
NYJ
-1.5
@DET
+6
@MIA
+4
CHI
+2.5
0.54
27.4%
0.1%
BUF
@CHI
+6.5
MIA
-1
SD
+3.5
@HOU
+4.5
@DET
+6
NE
+6
MIN
-3
@NYJ
+4
BYE
KC
+3
@MIA
+4
NYJ
-1
CLE
-2
@DEN
+12.5
GB
+6.5
@OAK
-2
@NE
+11
0.53
33.7%
0.1%
DAL
SF
+4.5
@TEN
+2
@STL
+5
NO
+5
HOU
-2
@SEA
+12.5
NYG
-0.5
WAS
-3
ARI
+1
@JAX
-1.5
BYE
@NYG
+4.5
PHI
+3
@CHI
+6.5
@PHI
+8
IND
+1
@WAS
+2.5
0.53
33.1%
0.1%
MIA
NE
+5
@BUF
+1
KC
+1.5
@OAK
-2.5
BYE
GB
+5.5
@CHI
+7
@JAX
-1
SD
+2.5
@DET
+5
BUF
-4
@DEN
+11
@NYJ
+2
BAL
+2
@NE
+10.5
MIN
-4
NYJ
-3.5
0.52
18.7%
0.3%
JAX
@PHI
+10
@WAS
+6
IND
+4.5
@SD
+11
PIT
+5.5
@TEN
+6
CLE
+0.5
MIA
+1
@CIN
+10
DAL
+1.5
BYE
@IND
+9.5
NYG
+2.5
HOU
+2
@BAL
+10.5
TEN
+1
@HOU
+7
0.49
30.1%
0.2%
OAK
@NYJ
+5.5
HOU
+3
@NE
+15
MIA
+2.5
BYE
SD
+7.5
ARI
+6
@CLE
+6.5
@SEA
+17
DEN
+10.5
@SD
+12.5
KC
+6.5
@STL
+10
SF
+11
@KC
+11.5
BUF
+2
@DEN
+15.5
0.49
30.9%
0.2%
NYG
@DET
+5.5
ARI
-1
HOU
-3.5
@WAS
+0.5
ATL
-1
@PHI
+6.5
@DAL
+0.5
BYE
IND
-0.5
@SEA
+11
SF
+4.5
DAL
-4.5
@JAX
-2.5
@TEN
+0.5
WAS
-4.5
@STL
+3.5
PHI
+1.5
0.49
27.7%
0.2%
CLE
@PIT
+6.5
NO
+6
BAL
+3.5
BYE
@TEN
+3
PIT
+3
@JAX
-0.5
OAK
-6.5
TB
+1
@CIN
+8
HOU
-1
@ATL
+7
@BUF
+2
IND
+2
CIN
+3
@CAR
+7
@BAL
+8.5
0.46
29.5%
0.3%
GB
@SEA
+6
NYJ
-10.5
@DET
-3
@CHI
-1.5
MIN
-12
@MIA
-5.5
CAR
-7.5
@NO
+2
BYE
CHI
-6.5
PHI
-5.5
@MIN
-7
NE
-3
ATL
-7.5
@BUF
-6.5
@TB
-4
DET
-8
0.40
24.6%
0.1%
IND
@DEN
+7.5
PHI
+0.5
@JAX
-4.5
TEN
-7
BAL
-2
@HOU
-1
CIN
-2.5
@PIT
+3
@NYG
+0.5
BYE
NE
+2
JAX
-9.5
WAS
-6
@CLE
-2
HOU
-6
@DAL
-1
@TEN
-2
In [70]:
df = pd.DataFrame([col.find({'div': {'class': 'dist'}}).string if col.find({'div': {'class': 'dist'}}) else None for col in row.find_all('td')] for row in table.find_all('tr'))
In [74]:
A = df.iloc[1:, 4:-1]; A.columns = xrange(17); A.index = xrange(32); A
Out[74]:
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
0
-7.5
-7.5
+4
None
-8
-6.5
-3
-6.5
+1.5
-10.5
-4
-11
-2.5
-12.5
-1.5
-2.5
-15.5
1
-6
-3
-4
None
-7.5
-12.5
-5.5
-5
-17
-11
-4
-10
+0.5
-2
-4.5
-5
-10.5
2
-5.5
+3.5
+3
+0.5
-6
-1
+3
+3.5
None
-5
+3
+7.5
-0.5
-3.5
-6
+5
+8
3
-6.5
+3
+1.5
-5.5
-5.5
-3
-7
-3
-2
-2.5
-2
None
+0.5
+2.5
+1.5
-3.5
-2.5
4
-5.5
+10.5
+1.5
-0.5
+7.5
+6.5
+10
-4
+6.5
+2.5
None
+1
-2
+1.5
+2
+5
+3.5
5
-10
-0.5
-8.5
+5.5
-6.5
-6.5
None
-0.5
-3
-6
+5.5
-9
-3
+2
-8
-3.5
-1.5
6
-4.5
-7
-3
-5.5
-7.5
-4
+3
None
-9
+1.5
-4.5
-11
-0.5
-11
+4.5
-6.5
-8
7
-5
-6.5
-15
-1.5
-6
-6
-10
-6
-1.5
None
-2
-7.5
+3
-0.5
-10.5
-5
-11
8
-6.5
+7
-1.5
+1.5
+1.5
+1.5
-7
+6
None
+6.5
-7.5
-5
+0.5
-6.5
+1.5
-5
-2.5
9
-4
+2.5
-5
None
+6.5
+4
+5.5
+4.5
+9
+4
+4
+5.5
-10
PK
-1.5
-3.5
+10.5
10
-3.5
+7.5
-1.5
+1.5
+7.5
None
+4
-4.5
-6.5
-3
+4
-6.5
+2.5
+2
-11.5
+3.5
-1.5
11
-3.5
+1
+3
None
+8
-6
-6
+0.5
-1
-4
-3
+10
+3
-2
+1.5
+5
+8
12
-3
-6
-11.5
-5
-8
None
-3
-2
-2
-1.5
-6
-5.5
-0.5
-7
-1.5
-7
-3
13
-2.5
-3
+3.5
-4.5
+2
+1
+7
+2
+3
None
+1
+1.5
-3.5
-2
+6
+2
-7
14
-2.5
-2.5
+4
+5.5
+8
+0.5
None
-5.5
-1
-1.5
+0.5
+5
PK
+3.5
+4
+4
+3
15
-1.5
-3
-3.5
-4
+2
-0.5
-4
+2.5
+2
-7
None
+5.5
-2.5
-2
-10.5
-2
-8.5
16
+1.5
-3.5
-7
None
+6
-3.5
+2.5
-2.5
-10
-8
+6
-1.5
PK
-2.5
-3
+2.5
+2.5
17
+2.5
-3.5
-1.5
+4
-1.5
+3.5
+7.5
+5
+2
+6
-2.5
None
-2
+7
-4
-7
+2.5
18
+2.5
-6
+8.5
-0.5
+7.5
+6
-3.5
+3
+1
None
-0.5
+11
+6
PK
+4.5
+3.5
-2.5
19
+3
+3.5
-4
-1.5
+1
-1.5
+4
-3.5
None
+1.5
+2.5
-7
-3
+7.5
-1.5
+7
-2.5
20
+3.5
+3
-3.5
-11
-7.5
-7.5
-4
+6.5
-2.5
None
-12.5
-5.5
+2.5
+0.5
+1.5
+6.5
+1.5
21
+3.5
-2
+7
+7
-3
-6
+3.5
-2
None
+7
+2
+9
+3.5
-0.5
-2
-1
+2
22
+4
+6.5
+11.5
+1.5
+12
+1
+3
+5.5
-1
None
+7.5
+7
+2
-1.5
+6
+4
+2.5
23
+6.5
-1
+3.5
+4.5
+6
+6
-3
+4
None
+3
+4
-1
-2
+12.5
+6.5
-2
+11
24
+4.5
+2
+5
+5
-2
+12.5
-0.5
-3
+1
-1.5
None
+4.5
+3
+6.5
+8
+1
+2.5
25
+5
+1
+1.5
-2.5
None
+5.5
+7
-1
+2.5
+5
-4
+11
+2
+2
+10.5
-4
-3.5
26
+10
+6
+4.5
+11
+5.5
+6
+0.5
+1
+10
+1.5
None
+9.5
+2.5
+2
+10.5
+1
+7
27
+5.5
+3
+15
+2.5
None
+7.5
+6
+6.5
+17
+10.5
+12.5
+6.5
+10
+11
+11.5
+2
+15.5
28
+5.5
-1
-3.5
+0.5
-1
+6.5
+0.5
None
-0.5
+11
+4.5
-4.5
-2.5
+0.5
-4.5
+3.5
+1.5
29
+6.5
+6
+3.5
None
+3
+3
-0.5
-6.5
+1
+8
-1
+7
+2
+2
+3
+7
+8.5
30
+6
-10.5
-3
-1.5
-12
-5.5
-7.5
+2
None
-6.5
-5.5
-7
-3
-7.5
-6.5
-4
-8
31
+7.5
+0.5
-4.5
-7
-2
-1
-2.5
+3
+0.5
None
+2
-9.5
-6
-2
-6
-1
-2
Content source: ltiao/notes
Similar notebooks: